home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Graphs / sa / a_digraph next >
Text File  |  1996-07-13  |  3KB  |  75 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY and is
  3. -- subject to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE
  4. -- contained in the file: Sather/Doc/License of the Sather
  5. -- distribution. The license is also available from ICSI, 1947 Center
  6. -- St., Suite 600, Berkeley CA 94704, USA.
  7. -- -------------------------------------------------------------------
  8. abstract class $RO_DIGRAPH{NTP} < $GRAPH{NTP,DIEDGE{NTP}} is
  9.    -- NTP is the type of the node i.e. the type of the unique node
  10.    -- index.  This is a read-only digraph abstraction. No modifying
  11.    -- operations are permitted. Most views of digraphs are of this
  12.    -- type
  13.    
  14.    
  15.    -- Inherits:
  16.    -- size: INT; str: STR; has(n: NTP): BOOL; elt!: NTP;
  17.    -- n_nodes:INT,n_edges:INT,n_adjacent(n: NTP): INT
  18.    -- node!: NTP, edge!:DIEDGE{NTP}, adjacent!(n:NTP):NTP
  19.    -- has_node(n: NTP):BOOL, has_edge(n:NTP):BOOL
  20.    
  21.    copy: $RO_DIGRAPH{NTP};
  22.    -- Create a copy of this digraph. The copy is also read-only
  23.    
  24.    n_incoming(n: NTP): INT;
  25.    -- Return the number of incoming edges into the node "n"
  26.    
  27.    n_outgoing(n: NTP): INT;
  28.    -- Return the number of outgoing edges from the node "n"
  29.  
  30.    --              ------ Cursor --------------------------
  31.    incoming!(once n: NTP): NTP;
  32.    -- Yield the incoming edges into the node "n". No ordering
  33.    -- is guaranteed
  34.    
  35.    outgoing!(once n: NTP): NTP;
  36.    -- Yield the outgoing edges from the node "n"
  37.    
  38.    -- Equality testing
  39.    equals(g: $RO_DIGRAPH{NTP}): BOOL;
  40.    -- Return true if the self and "g" have the same structure and the
  41.    -- same nodes. The nodes must be the *same* (i.e. =), and in
  42.    -- both graphs the must be the same edges between nodes
  43.    
  44. end;
  45. -------------------------------------------------------------------   
  46. abstract class $DIGRAPH{NTP} < $RO_DIGRAPH{NTP}  is
  47.    -- A directed graph that permits the addition of new nodes and edges.
  48.  
  49.    add_node: NTP;
  50.    -- Add a new node to the graph. Returns the node index
  51.  
  52.    add_node(n: NTP): NTP;
  53.    -- Add the node "n" to the graph. Return a node index.  The node
  54.    -- index that is returned may be the same as the original node
  55.    -- index, if that is appropriate for this graph, or maybe a new
  56.    -- object.  The user of this function should make no assumption
  57.    -- about the relationship between the node that is added and the
  58.    -- index that is returned.
  59.    
  60.    connect(e: DIEDGE{NTP});    
  61.    -- Add the edge "e" which connects the nodes "e.first" to
  62.    -- "e.second"
  63.  
  64.    delete_node(n: NTP);
  65.    -- Delete the node index "n"
  66.  
  67.    disconnect(e: DIEDGE{NTP});    
  68.    -- Delete the edge specified by "e". Does nothing if
  69.    -- "e" does no exist
  70.  
  71. end;
  72. ------------------------------------------------------------------- 
  73.  
  74.    
  75.